﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    /// <summary>
    /// 最长公共前缀
    /// </summary>
    public class LongestCommonPrefix : IRun
    {
        public void Run()
        {
          string s1 =   Method1(new string[]{ "aa","a","abc"});
        }

        public string Method1(string[] strs)
        {
            // 编写一个函数来查找字符串数组中的最长公共前缀。
            // 如果不存在公共前缀，返回空字符串 ""。

            if (strs.Length <= 0)
                return "";
            if (strs.Length == 1)
                return strs[0];

            string _Demo = strs[0];
            for (int i = 1; i < strs.Length; i++)
            {
                if (strs[i].Length == 0)
                    return "";

                for (int n = 0; n < (_Demo.Length > strs[i].Length ? strs[i].Length : _Demo.Length); n++)
                {
                    if (_Demo[n] != strs[i][n])
                    {
                        _Demo = _Demo.Substring(0, n);
                        break;
                    }
                    else if (n == (_Demo.Length > strs[i].Length ? strs[i].Length : _Demo.Length) - 1 && _Demo.Length > strs[i].Length)
                    {
                        _Demo = _Demo.Substring(0, _Demo.Length > strs[i].Length ? strs[i].Length : _Demo.Length);
                    }
                }

                //while (strs[i].IndexOf(_Demo) == -1)
                //{
                //    _Demo = _Demo.Substring(0, _Demo.Length - 1);
                //    if (_Demo == string.Empty)
                //        return "";
                //}
            }

            return _Demo;
        }

        public string Method2(string[] strs)
        {
            // 编写一个函数来查找字符串数组中的最长公共前缀。
            // 如果不存在公共前缀，返回空字符串 ""。

            if (strs.Length <= 0)
                return "";
            if (strs.Length == 1)
                return strs[0];

            char _Char;
            string _Demo = strs[0];
            for (int i = 0; i < _Demo.Length; i++)
            {
                _Char = _Demo[i];
                for (int n = 1; n < strs.Length; n++)
                {
                    // 若匹配char的Index，达到当前字符串尾，截取并返回；
                    // 若匹配char，与当前字符串对应位置的char不同，截取并返回；
                    if (i == strs[i].Length || strs[n][i] != _Char)
                        return _Demo.Substring(0,i);
                }
            }
            return _Demo;
        }
    }
}
